/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), cmp_stable);// sort不稳定
        return logs;
    }

    /**
     * @brief 排序规则
     * 1. 字母日志先于数字日志；
     * 2. 字母日志按字母数字顺序排列，先按内容排序，再按标识符排序；
     * 3.数字日志的顺序保持不变。
     */

    static bool cmp_stable(const string &a, const string &b){
        int pa = a.find(' ')+1;
        int pb = b.find(' ')+1;
        bool aIsNumberLog = isdigit(a[pa]);
        bool bIsNumberLog = isdigit(b[pb]);
        string aStr = a.substr(pa, a.size()-pa);
        string bStr = b.substr(pb, b.size()-pb);

        // 都是字母日志
        if (!aIsNumberLog && !bIsNumberLog) {
            int cmp = aStr.compare(bStr);
            if (cmp==0) return a.compare(b) <= 0;  // 小于0返回true
            return cmp <= 0;
        }
        // 一个是字母一个是数字--以a为中心，比a大的为true
        if(!aIsNumberLog && bIsNumberLog) return true;
        if(aIsNumberLog && !bIsNumberLog) return false;

        // 都是数字
        if(aIsNumberLog && bIsNumberLog) return false; // return false 的话，若a和b都是数字日志且相等，那么它们将会保持原来的顺序。
    }
};


// class Solution {
// public:
//     vector<string> reorderLogFiles(vector<string>& logs) {
//         stable_sort(logs.begin(), logs.end(), cmp_stable);
//         return logs;
//     }
//     static bool cmp_stable(const string &a, const string &b){
//         int pa = 0;
//         int pb = 0;
//         while(a[pa++] != ' ');
//         while(b[pb++] != ' ');
//         bool aIsNumberLog = a[pa] >= '0' && a[pa] <= '9';
//         bool bIsNumberLog = b[pb] >= '0' && b[pb] <= '9';
        
//         if(!aIsNumberLog && bIsNumberLog) return true;
//         if(aIsNumberLog && !bIsNumberLog) return false;
//         if(aIsNumberLog && bIsNumberLog) return false; // return false 的话，若a和b都是数字日志且相等，那么它们将会保持原来的顺序。

//         int cmp = a.compare(pa, -1, b, pb, -1);
//         if(cmp == 0) return a.compare(0, pa, b, 0, pb) <= 0;
//         else if(cmp < 0) return true; // a is lower
//         else return false;
//     }
// };



int main(int argc, const char** argv) {
    Solution solu = Solution();
    // 常见边界值
    // cout << INT32_MAX << endl;
    // cout << INT32_MIN << endl;
    // cout << INT_MAX << endl;
    // cout << INT_MIN << endl;
    int target = 7;
    vector<int> nums = {2,3,1,2,4,3};
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    // cout << solu.minSubArrayLen(target, nums) << endl;
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}